
 /*
Date:20210429 14:57PM
key:快慢指针，慢的一停一走，用mod2控制，快的一直走。每次比较二者是不是相等。
    先检测有无环。有环情况下，quick指针一定在环内。
    head一步一步走，quick指针转一圈看看head在不在一圈内，再就是第一个。
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head)
    {
        if(head==NULL){return NULL;}
        if(head->next==head){return head;}
        ListNode* quick=head;
        ListNode* slow=head;
        int i=2;
        bool cyc=0;
        while(quick!=NULL)
        {
            if(i%2){slow=slow->next;}
            quick=quick->next;
            if(quick==slow){cyc=1;break;}
            i++;
        }   
        //cout<<cyc;
        if(cyc)
        {
            //如果cyc=1，上面的quick最后一定在这个循环链表里。
            //这时从head开始，一步一步往前走
            ListNode* p=head;

            while(1)
            {
                //在已知循环内转一圈.
                ListNode* p1=quick;
                
                for(int i=0;;i++)
                {
                    if(i!=0)
                    {
                        if(p1==quick){break;}
                    }
                    if(p1==p){return p;}
                        p1=p1->next;
            
                }
                //没找到就是p还没进到环
                p=p->next;
            }

        }
        else
        {
            return NULL;
        }


    }
};
